package class2;

/**
 * https://leetcode.cn/problems/single-number-iii/description/
 * 有两种数出现
 * 本题为Code08_SingleNumber的升级版,
 * 思路：
 * 假设数字 3（二进制 0011）和数字 5（二进制 0101）是我们要找的两个数字。我们知道它们的异或结果 bitFlag = 6（0110），然后使用 0010 来分割。
 * 对于 3（0011），第2位是 1，所以它被分到第一组。
 * 对于 5（0101），第2位是 0，所以它被分到第二组。
 */
public class Code08_TwoNumber_02 {
    public static void main(String[] args) {
        int[] arr = new int[]{4, 1, 2, 1, 2, 7, 7, 10};

        int res = 0;
        for (int i : arr) {
            res ^= i;
        }
        System.out.println(res);
        // 0010 1000
        // 1101 1000 &
        // 0000 1000
        int bitFlag = res & (-res);  // 利用这一位将数字分为两组,它指示了 res 中两个不同数字的最低位不同的位置

        int num1 = 0, num2 = 0;
        for (int i : arr) {
            if ((i & bitFlag) != 0) {
                num2 ^= i;
            } else {
                num1 ^= i;
            }
        }
        System.out.println("num1 = " + num1);
        System.out.println("num2 = " + num2);

        twoNumber(arr);
    }

    public static void twoNumber(int[] arr){
        int ans = 0;
        for (int e : arr) {
            ans ^= e;
        }
        int bit = ans & -ans; // 不同的标识位置
        int num = 0;
        for (int i : arr) {
            if ((bit & i) == 0) {
                num ^= i;
            }
        }
        System.out.println(num + " and " + (ans ^ num));
    }
}
